#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
void MySort(vector<int>& num);

class Solution{
    public:
    //只能处理较少数列的情况
    vector<int> ans1(vector<int>& num){
        MySort(num);
        int length = num.size();
        int num_count;
        int thr = length / 2;
        int p = 0;
        vector<int> ret = {};
        if(length > 1){
            for(int i = 1; i != length; i++){
                if(num[p] != num[i]){
                    num_count = i - p;
                    p = i;
                    if(num_count > thr){
                        ret.push_back(num[i-1]);
                    }
                }
            }
            if(p != length-1){
                num_count = length - p;
                if(num_count > thr){
                    ret.push_back(num[length-1]);
                }
            }
        }
        else{
            ret.push_back(num[0]);
        }
        
        return ret;
    }

    //排序--> 2/n处一定是出现次数最多的！！！
    int ans2(vector<int>& num){
        int length = num.size();
        sort(num.begin(), num.end());
        return num[length/2];
    }

    int ans3(vector<int>& num){
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for(int n: num){
            ++counts[n];
            if(counts[n] > cnt){
                majority = n;
                cnt = counts[n];
            }
        }
        return majority;
    }

    void show(vector<int>& num){
        int length = num.size();
        cout << "[" << ends;
        for(int i = 0; i!= length-1; i++){
            cout << num[i] << "," << ends;
        }
        cout << num[length-1] << "]" << endl;
    }
};
//排序 sort(num.begin(), num.end())
void MySort(vector<int>& num){
    int length = num.size();
    for(int i = 0; i < length-1; i++){
        for(int j = 0; j < length-i-1; j++){
            if(num[j] > num[j+1]){
                int temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }
}

void test1(){
    vector<int> num = {3, 3, 4};

    Solution s;
    vector<int> ret = s.ans1(num);
    s.show(ret);
    cout << s.ans2(num) << endl;
    cout << s.ans3(num) << endl;
}

void test2(){
    vector<int> num = {2, 2, 1, 1, 1, 2, 2};

    Solution s;
    vector<int> ret = s.ans1(num);
    s.show(ret);
    cout << s.ans2(num) << endl;
    cout << s.ans3(num) << endl;
}

int main(void){
    test1();
    test2();

    return 0;
}